  Com o objetivo de encontrar limites duais melhores para a relaxa\c c\~ao linear, iremos primeiro transformar
o problema original definido como um grafo n\~ao direcionado em um problema com grafo direcionado, para 
ent\~ao encontrar uma arboresc\^encia que conecte os v\'ertices dos grupos. \cite{chopra:94} mostram que os 
limites da relaxa\c c\~ao linear em um grafo direcionado s\~ao melhores que em grafos n\~ao direcionados.
  Os v\'ertices $ V_{SA} = V \cup \{r\}$ cont\'em os v\'ertices do grafo de entrada $G$ e um v\'ertice 
artificial $r$. O conjunto de arcos $A_{SA}$ cont\'em dois arcos direcionados $(i,j)$ e $(j,i)$ para cada 
aresta $(i,j) \in E$ mais um conjunto de arcos da raiz $r$ at\'e cada um dos v\'ertices em $V$. Uma 
solu\c c\~ao $T_{SA}$ para esse novo grafo tamb\'em \'e uma solu\c c\~ao no grafo original se 
$T_{SA}$ \'e uma arboresc\^encia enraizada em $r$ e o grau de $r$ em $T_{SA}$ \'e igual a 1.
  Esse problema foi modelado como Problema de Programa\c c\~ao Inteira e para isso foram introduzidas as 
vari\'aveis $x \in \{0,1\}^{\|A_{SA}\|}$, que tem valor 1 se o arco est\'a em $T_{SA}$ e 0 caso contr\'ario, 
e $y \in \{0,1\}^{\|V_{SA}-1\|}$, que tem valor 1 se o v\'ertice est\'a em $T_{SA}$ e 0 caso contr\'ario.
  Dessa forma, fica simples garantir a conectividade da solu\c c\~ao, pois para todo v\'ertice que esteja 
separado de $r$ por um $corte$ deve existir um arco atravessando esse $corte$. Uma formula\c c\~ao 
an\'aloga foi feita em \cite{fischetti:06} para o Problema da \'Arvore de Steiner com Coleta de Pr\^emios.

\begin{tabular}{ll}
Minimizar&$ \sum\limits_{ij \in A_{SA}} c_{ij} x_{ij} $\\

subject to&$\sum\limits_{i \in V_{SAk}}\sum\limits_{j \notin V_{SAk}} x_{ji} =  1, \forall k \in C$\\

&$\sum\limits_{i \in V_{SAk}} y_{i} \geq  1, \forall k \in C$\\
&$\sum\limits_{j \in V_{SA}} x_{ji} =  y_i, \forall i \in V_{SA} \setminus \{r\}$\\
&$\sum\limits_{i \in V_{SA}} x_{ri} =  1$\\
&$\sum\limits_{i \in V_{SA}} p_i y_{i} \geq  P_{min}$\\
&$\sum\limits_{i \in S}\sum\limits_{j \notin S} x_{ji} \geq  y_t, \forall t \in S,r \notin S, \forall S \subset V_{SA}$\\

&$x_{ij},y_i \in \{0,1\},\forall (i,j) \in A_{SA}, \forall i \in V_{SA}\setminus \{r\}.$

\end{tabular}

\subsection{Resolvendo a Relaxa\c c\~ao Linear}
Para resolver a relaxa\c c\~ao linear, as restri\c c\~oes de integralidade ser\~ao substitu\'idas por: 
$0 \leq y_i \leq 1, \forall i \in V_{SA} \setminus \{r\}$ e $0 \leq x_{ij} \leq 1, \forall (i,j) \in A_{SA}$.
\subsubsection{Inicializa\c c\~ao}
  Existe um n\'umero exponencial de restri\c c\~oes de Cut Set, por isso elas
n\~ao ser\~ao inseridas todas de uma vez. Ser\'a utilizado ent\~ao um algoritmo de separa\c c\~ao, descrito
adiante. Em seguida, s\~ao adicionas restri\c c\~oes do tipo: 
$x_{ij}+x_{ji}\leq y_i, \forall i \in V_{SA} \setminus \{r\},(i,j) \in A_{SA}$ que, apesar de aumentarem o modelo, 
diminuem o tempo da relaxa\c c\~ao linear, pois assim elas n\~ao v\~ao ser adicionadas de forma 
impl\'icita durante o algoritmo de separa\c c\~ao.
\subsubsection{Separa\c c\~ao}
  Durante o algoritmo de separa\c c\~ao s\~ao adicionadas CutSets que s\~ao violadas pela solu\c c\~ao 
corrente encontrada na relaxa\c c\~ao linear. Essas restri\c c\~oes que s\~ao violadas podem ser encontradas
em tempo polinomial usando algoritmo de fluxo m\'aximo em um grafo $G'$ com os arcos capacitados com 
os valores da solu\c c\~ao corrente.
  O algoritmo de separa\c c\~ao \'e descrito na Figura~\ref{fig:pseudo_sep}. Dado um grafo $G'=(V_{SA},A_{SA},x)$, 
procura-se uma desigualdade violada atrav\'es do algoritmo de fluxo m\'aximo para cada par
de v\'ertices $(r,t)$, onde $t \in V_{SA}$. O algoritmo $f = FluxoMaximo(G,x',r,t,S_r,S_t)$ retorna o valor
do fluxo $f$ e dois conjuntos de v\'ertices, $S_r$ e $S_t$, que representam o corte m\'inimo, onde $r \in S_r$ e $t \in S_t$.
Ent\~ao, se $f<y_t$, a restri\c c\~ao $\sum\limits_{i \in S_t}\sum\limits_{j \notin S_t} x_{ji} \geq  y_t$ \'e adicionada. O algoritmo terminar\'a quando n\~ao houver mais nenhuma desigualdade violada.

\begin{figure}[ht!]
\begin{center}
\small{
\fbox{
\begin{minipage}[b]{5.20 in}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\= \kill
\textbf{Procedimento} $\mathtt{Separacao(V_{SA},A_{SA},x)}$;\\
1\> \textbf{Para\_Todo} $t \in V_{SA},y_t > 0$ \textbf{fa\c ca}\\
2\>\> $f \leftarrow FluxoMaximo(G',x,r,t,S_r,S_t)$;\\
3\>\> \textbf{Se} $f < y_i$ \textbf{ent\~ao}\\
4\>\>\> Inserir a desigualdade  $\sum\limits_{i \in S_t}\sum\limits_{j \notin S_t} x_{ji} \geq  y_t$  ao PL;\\
5\>\> \textbf{Fim\_Se}; \\
6\> \textbf{Fim\_Para\_Todo}; \\
{\bf Fim}.
\end{tabbing}
\end{minipage}
}
}
\end{center}
\caption{Pseudo C\'odigo Separa\c c\~ao}
\label{fig:pseudo_sep}
\end{figure}

\subsection{Corte de Cobertura}
  Para aplicar o algoritmo de separa\c c\~ao de cobertura \`a desigualdade de 
pr\^emio m\'inimo ser\'a feita uma modifica\c c\~ao da mesma para uma desigualdade do 
problema da mochila cl\'assico. Para isso, iremos 
supor a cria\c c\~ao de uma vari\'avel $z_i = y_i - 1, \forall i \in V_{SA}\setminus \{r\}$. Sendo assim,
a desigualdade original passa a ser: $\sum\limits_{i \in V_{SA}} p_i z_{i} \leq  P_{total} - P_{min}$.
\subsubsection{Algoritmo}
  De forma an\'aloga \`a se\c c\~ao anterior, iremos procurar por uma desigualdade de cobertura 
que seja violada pela solu\c c\~ao corrente da relaxa\c c\~ao linear e iremos adicion\'a-la ao modelo. 
Para encontrar tal desigualdade violada, o seguinte problema de programa\c c\~ao inteira dever\'a ser resolvido:

\begin{tabular}{ll}
Minimizar&$w = \sum\limits_{i \in V_{SA}\setminus \{r\}} y_{i} u_{i}$\\

subject to&$\sum\limits_{i \in V_{SA}} p_i u_{i} \geq P_{total} - P_{min}+1$\\

&$u_i \in \{0,1\}, \forall i \in V_{SA}\setminus \{r\}.$

\end{tabular}

Para saber se a solu\c c\~ao desse problema viola alguma desigualdade de cobertura, basta verificar se 
a solu\c c\~ao \'otima $u^{R}$ tem $w < 1$ . Sendo satisfeita tal condi\c c\~ao, ser\'a adicionada a 
desigualdade de cobertura: $\sum\limits_{i \in R} p_i z_{i} \leq  \|R\| - 1$, que pode ser escrita 
em fun\c c\~ao de $y$ como: $\sum\limits_{i \in R} p_i y_{i} \geq 1$.

Esses novos cortes de cobertura ser\~ao procurados durante o algoritmo descrito na se\c c\~ao anterior: 
ou quando ele encontrar 
$k$ vezes solu\c c\~oes com o mesmo valor; ou quando n\~ao houver mais nenhuma desigualdade de cutset violada
pela solu\c c\~ao da relaxa\c c\~ao linear corrente.

